package algorithm.leetcode.simple;


/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020/9/1
 */
public class Question23 {
    public static void main(String[] args) {

        ListNode node = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode node1 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode node2 = new ListNode(2, new ListNode(6));
        ListNode[] nodes = {node, node1, node2};
        Question23 question = new Question23();
        ListNode node3 = question.mergeKLists(nodes);
        System.out.println(node3);

    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoList(l1, l2);
    }

    private ListNode mergeTwoList(ListNode l1, ListNode l2) {
        if (l1 == null){
            return l2;
        }
        if (l2 == null){
            return l1;
        }
        if (l1.val < l2.val){
            l1.next = mergeTwoList(l1.next, l2);
            return l1;
        }else {
            l2.next = mergeTwoList(l1, l2.next);
            return l2;
        }

    }


    private static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
